package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/decode-ways/
 *  解码方法  动态规划 动不出来啊
 * author: hongchen.liao
 * date:  2022/8/16
 */
public class _91_Decode_Ways {


    class Solution {
        public int numDecodings(String s) {
            int n = s.length();
            int[] f = new int[n+1];
            f[0] = 1;
            for(int i = 1; i <= n; i++){
                if(s.charAt(i-1) != '0'){
                    f[i] += f[i-1];
                }
                if(i > 1 && s.charAt(i-2) != '0' && ((s.charAt(i-2) - '0') * 10 + (s.charAt(i-1) - '0') <= 26)){
                    f[i] += f[i-2];
                }
            }
            return f[n];
        }
    }

    //状态压缩
    class Solution2 {
        public int numDecodings(String s) {
            int n = s.length();
            int a = 0, b = 1, c = 0;
            for(int i = 1; i <= n; i++){
                c = 0;
                if(s.charAt(i-1) != '0'){
                    c += b;
                }
                if(i > 1 && s.charAt(i-2) != '0' && ((s.charAt(i-2) - '0') * 10 + (s.charAt(i-1) - '0') <= 26)){
                    c += a;
                }
                a = b;
                b = c;
            }
            return c;
        }
    }



}
